The present invention relates to allocating buffers for data transmission in a network communication device constructed to direct network traffic. More particularly, the invention relates to allocating buffers in the network device based on port utilization and quality of service goals to achieve fair buffer usage.
Computer networks have been used by a large number of users to increase computing power, share resources and communicate. Computer networks include a number of computers or other devices located in one room or one building and connected by a local area network (LAN), such as Ethernet or Token Ring. LANs located in different locations can be interconnected by switches, routers, bridges, microwave links or satellite links to form a wide area network (WAN). Such a network may include hundreds of connected devices distributed over numerous geographical locations and belonging to different organizations.
One computer or video communication device can send data to another device using network communications devices (e.g., packet switches, routers, bridges) interconnected by transmission media or data links. Viewed from the outside, a network communications device includes input ports that receive data and output ports that send data over data links. Inside the network device, transmitted data is accepted at input ports, buffered and transferred internally, and eventually received at output ports for re-transmission over the next data link. This process uses various scheduling and arbitration algorithms for xe2x80x9cswitchingxe2x80x9d the data.
Typically, network communications devices transmit data in a standardized format, such as TCP/IP datagrams, frames, or ATM cells, which generally will be referred to as data units. Each data unit typically includes a header portion with addressing information and a body portion with transmitted data or payload. A data unit sent between network devices may, in general, vary in size depending on the type of the data unit. When a data unit arrives at an input port of a network communication device, a routing algorithm analyzes the header and makes a forwarding decision based on a destination address carried by the header.
In the process of forwarding data from an input port to an output port, different internal switching devices can use several temporary memories (called buffers). A communication device decides if an incoming data unit is buffered or dropped, based on the incoming data unit itself. This decision is performed at the line speed, and is executed after the start of the header and before the last bit of the data unit is received. This way the communication device can re-use the current buffer for the next data unit if decided that the current data unit will be dropped.
The buffers may simply be arranged into a single large pool of buffer units to be used for all received data units stored by the device. This arrangement assures that no data units will be arbitrarily dropped as long as there are available buffer units for storage. However, to this arrangement cannot effectively arbitrate access to several concurrent inputs and outputs. Alternatively, separate pools of buffers may be associated with input ports and output ports. Based on the location of buffers, there are generally three classes of data switching architectures: output buffered, input buffered, or combined input-output buffered architectures. The present invention is applicable to all three architectures.
An output buffered network device places data units, arriving at its input port, into different output buffers located at its output ports depending on the address of each data unit. An output buffered network device, having N input ports and receiving data at M bits per second, needs a data transmission rate of Nxc3x97M for the switching to ensure that data units are not lost (i.e., dropped). The buffers store the received data units when the transmission rate is lower.
Advantageously, output buffered network communication devices can use up to the full bandwidth of outbound data links because of the immediate forwarding of the received data units into output buffers. The data units are fed from output buffers to the output data links as fast as the links can accept them. However, when the transmission rate is lower than the reception rate, the communication device has to keep buffering the data units and may eventually run out of buffers. For a larger communication device having many input ports with a high link speed, the buffer capacity and speed must be increased proportionally in order to handle the combined data rates of all input ports being switched to different output ports. Increasing the buffer capacity and speed increases the cost of output buffered network devices.
A network communication device can assign one pool of buffers for each output port (or input port), which is commonly called xe2x80x9cper port queuingxe2x80x9d. In this arrangement, one port cannot interfere with another port""s performance. However, higher priority traffic may suffer a higher loss of data units (e.g., ATM cell, frames) then lower priority traffic. The data loss occurs even though there may be, for example, idle ports with available cell/frame buffers; this is the result of the buffer fragmentation.
Alternatively, the communication device can assign one pool of buffers for each priority, which is called xe2x80x9cper priority queuingxe2x80x9d. In this arrangement, higher priority traffic will not suffer data unit loss because of over-subscription of lower priority traffic. However, the buffers allocated to higher priority traffic may not be available to lower priority traffic when the higher priority traffic is idle. In another arrangement, the communication device can assign one pool of buffers for each priority for each output port (or input port). This is called xe2x80x9cper port and priority queuingxe2x80x9d. Advantageously, a given port and priority will only drop data units due to the action of data streams using that port and priority. However, this arrangement fragments buffer queues and thus buffers may be used inefficiently. For example, buffer units may be assigned to ports and priorities that are currently idle, and thus buffer units are left unused. Therefore, efficient buffer allocation becomes very important.
A network communication device can also use an input buffered architecture. Popular input buffered devices use non-blocking input buffered switching called the crossbar. The input buffered crossbar has a crossbar fabric running at a speedup of 1 (i.e., equal to link rate). However, if each input port maintains a single FIFO queue, data suffer from head-of-line blocking. This blocking limits the maximum achievable throughput and is relatively inflexible. To eliminate head-of-line blocking, input ports can have virtual output queues (VOQs). Inputs ports with VOQs have a bank of queues with one queue per output port. Data units are stored in random access buffers at the input ports, and pointers to the data are stored in the respective VOQs. Buffer allocation becomes again important.
Asynchronous transfer mode (ATM) switching technology enables fast data switching for wide ranges of traffic demands. ATM can carry virtually any type of information that can be expressed in a digital form, ranging from voice telephone traffic, to real-time video, to high-speed file transfers, etc. ATM based networks may eliminate the need for different networks to carry different types of traffic. ATM transfer is asynchronous in the sense that the recurrence of ATM cells, which carry transferred information, is not necessarily periodic. Each communication device that uses the ATM network submits an ATM cell for transfer when it has a cell to send. Once aggregated and scheduled, the ATM cells ride in synchronous slots on a high-speed media, such as a SONET optical fiber.
ATM organizes digital data into cells having a fixed length and format. Each ATM cell includes a header, primarily for identifying cells relating to the same virtual connection, and the transmitted data or payload. The ATM standard defines a cell size that is 53 bytes or octets. The first five bytes of each ATM cell form the header, and the remaining 48 bytes represent payload data. The header of each ATM cell includes a field for a virtual path identifier (VPI) and a virtual circuit identifier (VCI). The VPI and VCI together identify the particular circuit or a communication path to which each cell relates.
Within a transport stream, the VPI and VCI identifiers direct the stream into separate logical or xe2x80x98virtualxe2x80x99 paths and segregate traffic within each virtual path into logical or xe2x80x98virtualxe2x80x99 circuits. Within one or more virtual path connections, an ATM communication device makes the virtual circuit connections available to transport any number of individual communications. Such logical circuit connections are set up (i.e., opened) and closed, as needed, to efficiently provide a required transport capacity for independent communication sessions for a number of separate communication devices.
A network communication device can treat all data units equally, that is, all data units can have the same priority when traveling over a network. Alternatively, different data units can have various levels of the quality of service (QoS). This concept has been applied to ATM networks (and to other network formats to some extent). The measures of QoS include a cell loss rate, a cell transfer delay, bandwidth, and other. The cell loss rate reflects the number of cells that are lost, for example, when more cells arrive at a switch than can be accommodated in the switch""s buffer. The cell transfer delay reflects the amount of time a cell spends at a switch (or other storage and/or transfer device) before being re-transmitted. For example, if a cell sits in a buffer for a long period of time while other (e.g., higher QoS level) cells are transmitted, the cell transfer delay of this cell is the amount of time it spends in the buffer. Other measures of QoS may include a cell delay variation (i.e., the amount of variation in cell delay) or a maximum cell transfer delay (rather than an average cell transfer delay).
Furthermore, different types of information require different transport rates of data. For example, real-time video transmission requires a high constant bit rate or a high variable bit rate to maintain synchronism, but packet data communications, in general, do not require a constant or variable bit rate. Similarly, voice communication (which usually produces bursty data traffic) requires real-time transmission, but can tolerate some cell loss without having a detrimental impact. On the other hand, a loss of a small number of cells in file transfer, such as e-mail, requires re-transmission of the entire file. Therefore, a network communication device also needs to optimally assign buffers associated with individual connections to take into account the different types of information. Furthermore, a network communication device needs to decide whether a new connection can be opened, and the device needs to allocate (re-assign) optimally buffers when such a connection is opened.
Therefore, there is a need for a network communication device and method that can efficiently allocate buffers for data transmission.
The present invention is a novel network communication device for directing network traffic and a novel method for allocating buffer units in a network communication device. The novel device or method allocate buffer units based on port utilization and quality of service goals to achieve fair buffer usage.
In one aspect, a network communication device for directing data units over a communication network includes at least one input and/or output port arranged to receive and transmit data units, a plurality of buffer units divided into several sub-pools, and a buffer allocator for allocating buffer units between the sub-pools. The buffer allocator is arranged to determine a priority value for each sub-pool based on quality of service parameter for each connection established at at least one input port. The buffer allocator is also arranged to determine a utilization value of the input port, and arranged to allocate buffer units for each sub-pool based on the priority value and based on the utilization value, wherein a minimal number of connections established at a most utilized port will suffer loss of data units while receiving the data units.
In another aspect, a computer-readable medium includes a representation of an algorithm used in a network communication device constructed for directing data units over a communication network. The network communication device includes a plurality of buffer units divided into sub-pools, and at least one input and/or output port connected to the communication network and arranged to receive and transmit data units. The algorithm for allocating buffer units between the sub-pools includes the steps of:
determining a priority value for each sub-pool based on a quality of service parameter for each connection established at at least one input port;
determining a utilization value of the input port; and
allocating buffer units for each sub-pool based on the priority value and based on the utilization value, wherein a minimal number of connections established at a most utilized port will suffer loss of data units while receiving the data units.
Another aspect is a method for dynamically managing buffer units assigned to sub-pools of a network communication. The network communication includes at least one input and/or output port connected to a communication network and arranged to receive and transmit data units. The network communication device also includes a plurality of buffer units divided into several sub-pools for buffering the data units. The method includes specifying a priority value for each sub-pool based on at least one quality of service parameter for transmitting the data units from the at least one port; determining a utilization value of at least one input port; and allocating buffer units for each of the sub-pools based on the priority value and based on the utilization value, wherein a minimal number of the data units will be lost during reception or transmission of the data units at a most utilized port of the network communication device.
Preferred embodiments of the above aspects include one or more of the following features:
The buffer allocator is arranged to determine the priority value of the sub-pool based on all connections having the same quality of service parameter and being established at the port. The buffer allocator is further arranged to assign the allocated buffer units to each of the sub-pools for use by the connections.
The network communication device is further arranged to establish a new connection using the buffer units assigned to one of the sub-pools. The quality of service parameter relates to a type of bit rate handled by the connection.
The utilization value is calculated as a port line speed minus an aggregate peak cell rate for an under-subscribed port having the port line speed larger than the aggregate peak cell rate. The utilization value is calculated as an aggregate steady state cell rate minus a port line speed for a fully-subscribed port having an aggregate steady state cell rate smaller than its port line speed and its port line speed smaller than the aggregate peak cell rate. The utilization value is calculated as an inverse of (an aggregate steady state cell rate minus a port line speed) for a fully-subscribed port having the aggregate steady state cell rate larger than its port line speed.
The network communication device may be a circuit switch, a bridge, or a router using a connection oriented protocol, or may be another similar device arranged to direct data units transferred from an origination device to a destination device over a communication network.
The network communication device is further arranged to establish a new connection after the buffer allocator determines the quality of service parameter for the new connection, determines the number of the buffer units required for the new connection, and borrows the number of the buffer units from other sub-pools using a precedence order of the sub-pools. The borrowing of the number of the buffer units from other sub-pools includes establishing a precedence order of the sub-pools.
The precedence order includes:
Initially:
1. Borrow the available buffer units of its own pool, i.e., buffer assigned to a sub-pool but not allocated to an existing connection.
2. Borrow all available assigned buffer units from disabled ports.
For Each Under-subscribed (US) Port Borrow Buffer Units from Sub-pools in the Following Order:
1. Borrow buffer units available from all sub-pools with lower priority of all participating ports.
2. Borrow buffer units assigned to unspecified bit rate (UBR) sub-pools from over-subscribed (OS) ports.
3. Borrow buffer units assigned to UBR sub-pools from fully-subscribed (FS) ports.
4. Borrow buffer units assigned to UBR sub-pools from US ports with a lower metric value.
5. Borrow buffer units assigned to available bit rate (ABR) ports.
6. Borrow buffer units assigned to sub-pools having lower priorities from the same port.
For Each FS Port, Borrow Buffer Units From Sub-pools in the Following Order:
1. Borrow buffer units available from all-sub-pools with lower priority of all participating ports.
2. Borrow buffer units assigned to UBR sub-pools of OS ports.
3. Borrow buffer units assigned to UBR sub-pools of other FS ports with a lower metric value.
4. Borrow buffer units assigned to sub-pools of any lower priority of the same port.
For Each OS Port, Borrow Buffer Units From Sub-pools in the Following Order:
1. Borrow buffer units available from sub-pools from other priorities of the same port.
FIG. 1 shows diagrammatically a computer network.
FIG. 2 shows diagrammatically a network switch used in the computer network of FIG. 1.
FIG. 3 shows a block diagram of a network interface module (ANIM).
FIGS. 4 and 4A are high level flow diagrams of an adaptive buffer management algorithm.